package com.demo.java.OD351_400.OD358;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【乘坐保密电梯(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146165468
 */
public class OdMain {
    public static void main(String[] args) {
        // 输入读取
        Scanner scanner = new Scanner(System.in);
        String input1 = scanner.nextLine();
        String input2 = scanner.nextLine();

        // 处理输入数据
        List<Integer> params = splitInput(input1);
        List<Integer> nums = splitInput(input2);
        int target = params.get(0);
        int count = params.get(1);

        // 计算数字的总和，并计算出所需的数量和和
        int sum = nums.stream().mapToInt(Integer::intValue).sum();
        int requiredUpCount = count / 2 + count % 2;  // 需要选择的上升部分个数
        int requiredUpSum = (sum + target) / 2;  // 计算所需的上升部分总和

        // 对数字进行降序排序
        Collections.sort(nums, Comparator.reverseOrder());

        // 回溯寻找所有可能的排列路径
        List<List<Boolean>> paths = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(Collections.nCopies(count, false)), 0, 0,
                requiredUpCount, requiredUpSum, paths);

        // 构造结果路径
        List<List<Integer>> result = new ArrayList<>();
        for (List<Boolean> path : paths) {
            result.add(constructSequence(path, nums));
        }

        // 对结果路径进行排序
        result.sort(OdMain::compareSequences);

        // 输出最优路径
        List<Integer> optimalSequence = result.get(0);
        printSequence(optimalSequence);
    }

    // 处理输入的字符串，并转换为整数列表
    private static List<Integer> splitInput(String input) {
        List<Integer> values = new ArrayList<>();
        String[] parts = input.split(" ");
        for (String part : parts) {
            values.add(Integer.parseInt(part));
        }
        return values;
    }

    // 回溯算法，寻找符合条件的所有路径
    private static void backtrack(List<Integer> nums, int index, List<Boolean> path,
                                  int sum, int count, int requiredUpCount, int requiredUpSum,
                                  List<List<Boolean>> paths) {
        if (count > requiredUpCount) {
            return;
        }

        if (count == requiredUpCount) {
            if (sum < maxUpSumBelowTarget) {
                return;
            }
            if (sum > maxUpSumBelowTarget) {
                maxUpSumBelowTarget = sum;
                paths.clear();
            }
            paths.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < nums.size(); i++) {
            int num = nums.get(i);

            if (sum + num > requiredUpSum) {
                continue;
            }

            path.set(i, true);  // 标记当前数字被选择
            backtrack(nums, i + 1, path, sum + num, count + 1, requiredUpCount,
                    requiredUpSum, paths);  // 递归调用
            path.set(i, false);  // 回溯，撤销选择
        }
    }

    // 构建最终的排列序列
    private static List<Integer> constructSequence(List<Boolean> path,
                                                   List<Integer> nums) {
        List<Integer> up = new ArrayList<>();
        List<Integer> down = new ArrayList<>();

        for (int i = 0; i < nums.size(); i++) {
            if (path.get(i)) {
                up.add(nums.get(i));
            } else {
                down.add(nums.get(i));
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.size() / 2; i++) {
            res.add(up.get(0));
            up.remove(0);
            res.add(down.get(0));
            down.remove(0);
        }

        if (!up.isEmpty()) {
            res.add(up.get(0));
            up.remove(0);
        }

        return res;
    }

    // 最大的上升和，初始为0
    private static int maxUpSumBelowTarget = 0;

    // 比较两个路径的大小
    private static int compareSequences(List<Integer> sequence1,
                                        List<Integer> sequence2) {
        for (int i = 0; i < sequence1.size(); i++) {
            if (!Objects.equals(sequence1.get(i), sequence2.get(i))) {
                return Integer.compare(sequence1.get(i), sequence2.get(i));
            }
        }
        return 0;
    }

    // 输出最终的排列结果
    private static void printSequence(List<Integer> sequence) {
        for (int i = 0; i < sequence.size(); i++) {
            System.out.print(sequence.get(i));
            if (i != sequence.size() - 1) {
                System.out.print(" ");
            }
        }
    }
}